#include <iostream>
using namespace std;

typedef long long ll;

int n, a, b, p; //获取输入

ll quick_pow(int a, int b, int p)
{
    ll res = 1, t = a;
    while (b)
    {
        if (b & 1) //如果b的现在的二进制数的个位是1
            res = res * t % p;
        t = t * t % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    cin >> n;
    while (n--)
    {
        cin >> a >> b >> p;
        cout << quick_pow(a, b, p) << endl;
    }
    return 0;
}